import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;

public class Solution436 {

    private int[] binarySearchCeiling(int[][] sortInterval, int target){
        int left = 0, right = sortInterval.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            int[] tmpInterval = sortInterval[mid];
            int midVal = tmpInterval[0];
            if(midVal < target){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        return 0 <= right && right < sortInterval.length ? sortInterval[right] : null;
    }

    public int[] findRightInterval(int[][] intervals) {
        final int length = intervals.length;
        int[][] sortIntervals = new int[length][2];
        for (int i = 0; i < length; i++) {
            sortIntervals[i] = new int[]{intervals[i][0], i};
        }
        Arrays.sort(sortIntervals, (int[] o1, int[]o2) -> { return o1[0] < o2[0] ? -1 : 1; });
        int[] res = new int[length];
        for(int i = 0; i < length; i++){
            int[] ceiling = binarySearchCeiling(sortIntervals, intervals[i][1]);
            if(ceiling == null){
                res[i] = -1;
            }
            else {
                res[i] = ceiling[1];
            }
        }
        return res;
    }
}
